package listbyorder.access001_100.test87;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/5 9:37
 */
public class Solution1 {

    // 暴力递归————超时
    public boolean isScramble(String s1, String s2) {
        if (s1.equals(s2)) return true;
        if (s1.length() != s2.length()) return false;
        return getAns(s1, s2, 0, s1.length(), 0, s2.length());
    }

    private boolean getAns(String s1, String s2, int c1, int e1, int c2, int e2) {
        if (c1 + 1 == e1) return s1.charAt(c1) == s2.charAt(c2);
        for (int i = 1; i < e1 - c1; i++) {
            if ((getAns(s1, s2, c1, c1 + i, c2, c2 + i) && getAns(s1, s2, c1 + i, e1, c2 + i, e2))
                    || (getAns(s1, s2, c1, c1 + i, e2 - i, e2) && getAns(s1, s2, c1 + i, e1, c2, e2 - i))) {
                return true;
            }
        }
        return false;
    }
}
